# 在给定的网格中，每个单元格可以有以下三个值之一：
#
# 值 0 代表空单元格；
# 值 1 代表新鲜橘子；
# 值 2 代表腐烂的橘子。
# 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
#
# 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
#


# 输入: [[2,1,1],[1,1,0],[0,1,1]]
# 输出: 4

# 输入: [[2,1,1],[0,1,1],[1,0,1]]
# 输出: -1

# 输入: [[0,2]]
# 输出: 0
# https://leetcode-cn.com/problems/rotting-oranges


# 不仅垃圾 还跪了...我是菜狗无误
def orangesRotting(grid) -> int:
    count_x = -1
    bad_list = []
    count_time = 0
    check_single = False
    for inner in grid:
        count_x += 1
        count_y = -1
        for single in inner:
            count_y += 1
            # grid[count_x][count_y]
            if single == 2:
                bad_list.append([count_x, count_y])
            elif single == 1:
                check_single = True
    # 这一步为止取到了原始烂橘子的数量
    if not check_single:
        return 0
    change = True
    while change:
        has_change = False
        bad_list_puls = []
        for x, y in bad_list:
            try:
                if x == 0:
                    if grid[x + 1][y] == 1:
                        grid[x + 1][y] = 2
                        bad_list_puls.append([x + 1, y])
                        has_change = True
                elif x == count_x:
                    if grid[x - 1][y] == 1:
                        grid[x - 1][y] = 2
                        bad_list_puls.append([x - 1, y])
                        has_change = True
                elif 0 < x < count_x:
                    if grid[x - 1][y] == 1:
                        grid[x - 1][y] = 2
                        bad_list_puls.append([x - 1, y])
                        has_change = True
                    if grid[x + 1][y] == 1:
                        grid[x + 1][y] = 2
                        bad_list_puls.append([x + 1, y])
                        has_change = True

                if y == 0:
                    if grid[x][y + 1] == 1:
                        grid[x][y + 1] = 2
                        bad_list_puls.append([x, y + 1])
                        has_change = True
                elif y == count_y:
                    if grid[x][y - 1] == 1:
                        grid[x][y - 1] = 2
                        bad_list_puls.append([x, y - 1])
                        has_change = True
                elif count_y > y > 0:
                    if grid[x][y - 1] == 1:
                        grid[x][y - 1] = 2
                        bad_list_puls.append([x, y - 1])
                        has_change = True
                    if grid[x][y + 1] == 1:
                        grid[x][y + 1] = 2
                        bad_list_puls.append([x, y + 1])
                        has_change = True
                else:
                    pass
            except:
                return count_time
        else:
            if not has_change:
                for check in grid:
                    if 1 in check:
                        return -1
                return count_time
            else:
                count_time += 1
                bad_list[:] = bad_list_puls


re = orangesRotting([[1,2]])
print(re)   # 0 期待值是1
